Internet protocol networks, often referred to as IP networks, are used to transmit data throughout the United States and around the world. IP networks may transmit packets of data for Internet use, but also may carry any other type of data in IP format, such as voice telecommunications using voice-over-IP protocols.
IP networks may comprise very high bandwidth transport media, such as optical fibers, that serve as links to connect points of presence, often referred to as PoPs. Within a PoP, one or more routers receive and direct packets over the links. A link has two ends, each of which terminates with a router in a PoP. Each link connects a pair of routers and transmits data packets between those two routers. Some links are inter-PoP links that connect routers in different PoPs. Other links are intra-PoP links that connect routers within the same PoP.
A router may be thought of as being “adjacent” to another router if they are separated by only one link. Adjacent routers may be in different PoPs, or may be in the same PoP. A router may receive a data packet over a link from the adjacent router connected to it by that link. Each router independently determines how to route a packet. Routing decisions may be made based upon weights assigned to the links by the network operator. Using methods and protocols well-known in the art, the receiving router will then determine how to forward the received data packet over a link to another router. A data packet bound for a destination node in an IP network accordingly “hops” along the links of an IP network from router to router until it reaches its destination.
While IP networks perform well under most circumstances, link overload is a problem that can impair the function of IP networks and, in turn, interfere with the practices of those using an IP network to carry data. Experience with existing IP networks indicates that the incidence of link overload in an IP network is often very low. However, experience with existing IP networks further indicates that at least a few links in an IP network are likely to be overloaded at any given time, as the number of links in an IP network is so large that even a very low incidence of link overload implies that at any given time a few links in an IP network are likely to be overloaded. Link overload may occur for a variety of reasons, such as the failure of an adjacent link due to physical damage, unexpected fluctuations in network traffic, denial of service attacks, or other causes. When a link becomes congested, it would be desirable to route data packets around the congested link, even if the route used to deflect the packet around the congested link is longer than the route through the congested link. Such a routing method would prevent the data packet from being slowed by the congested link and would allow the congestion on the overloaded link to dissipate, thereby improving network performance.